A Decentralized High Performance Time Service Architecture

A time service is a means by which users, applications, etc. obtain values associated with some measurement of elapsed time from some agreed on event. In a relativistic world, time services are necessarily imperfect, there being no such thing as simultaneity. In this paper we discuss an architecture for delivering required time services to a collection of heterogeneous machines communicating over a wide area network consisting of multiply connected and overlapping local area networks with various communication media. The primary building block of our architecture is a logical clock. We explain how logical clock objects simplify the treatment and resolution of a number of problems associated with time services. Having used logical clock objects to decouple clock synchronization problems from problems associated with smoothness and conformity to political time, we provide a straightforward master-slave algorithm for clock synchronization and show how to transform it into an eavesdropping algorithm that takes advantage of the broadcast nature of most local area networks to dramatically reduce message overhead. Finally, we show how to integrate eavesdropping and regular clock synchronization algorithms into a fault tolerant network time service that tolerates and coordinates multiple master clocks or external sources of time.